P2261 [CQOI2007]余数求和

题目要求的是

i=1nk mod i\sum_{i=1}^nk~mod~i

i=1nkkii\Rightarrow \sum_{i=1}^n k-\lfloor \frac{k}{i} \rfloor * i

nki=1nkii\Rightarrow n*k-\sum_{i=1}^n \lfloor \frac{k}{i} \rfloor * i

然后 ,因为在lrl-r区间内ki\lfloor \frac{k}{i} \rfloor的值相等,ii递增,所以这段区间内是一个等差数列 ( 首项为 lkil*\lfloor \frac{k}{i} \rfloor , 末项为 rkir * \lfloor \frac{k}{i} \rfloor , 公差为 ki\lfloor \frac{k}{i} \rfloor ) , 对于每一段区间计算和即可。

注意,AnsAns 计算的是i=1nkii\sum_{i=1}^n \lfloor \frac{k}{i} \rfloor * i

#include <cstdio>
#include <iostream>
using namespace std;

int n , k;
long long Ans;

int main( ) {
	scanf("%d %d",&n,&k);
	for( int l = 1 , r ; l <= n ; l = r + 1 ) {
		r = k / l == 0 ? n : min( n , k / ( k / l ) );
		Ans += 1ll * ( k / l ) * ( l + r ) * ( r - l + 1 ) / 2; 
	}
	printf("%lld", 1ll * n * k - Ans );
	return 0;
}